import java.util.*;

/*
给定一个长度为 N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式
第一行包含整数 N，表示数列长度。第二行包含 N个整数，表示整数数列。

输出格式
共一行，包含 N个整数，其中第 i 个数表示第 i个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围
1≤N≤1e5  1≤数列中元素≤1e9

输入样例：
5
3 4 2 7 5

输出样例：
-1 3 -1 2 2

 */
//单调栈
//public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        Stack<Integer> stk = new Stack<>();
//        //循环，如果i<j且a[i]>a[j],则剔除a[i]
//        for (int i = 0; i < n; i++) {
//            int x = sc.nextInt();
//            while (!stk.isEmpty() && stk.peek() >= x) stk.pop();
//            if (!stk.isEmpty()) System.out.print(stk.peek() + " ");
//            else System.out.print("-1 ");
//            stk.push(x);
//        }
//    }
//}

/*
给定一个大小为 n≤1e6的数组。
有一个大小为 k的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 kk 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n个整数，代表数组的具体数值。
同行数据之间用空格隔开。

输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：
8 3
1 3 -1 -3 5 3 6 7

输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7

 */

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 求最小值
        Deque<Integer> minDeque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 移除窗口外的元素
            while (!minDeque.isEmpty() && minDeque.peekFirst() <= i - k) {
                minDeque.pollFirst();
            }
            // 移除队尾比当前元素大的元素
            while (!minDeque.isEmpty() && arr[minDeque.peekLast()] >= arr[i]) {
                minDeque.pollLast();
            }
            minDeque.offerLast(i);
            if (i >= k - 1) {
                System.out.print(arr[minDeque.peekFirst()] + " ");
            }
        }
        System.out.println();

        // 求最大值
        Deque<Integer> maxDeque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 移除窗口外的元素
            while (!maxDeque.isEmpty() && maxDeque.peekFirst() <= i - k) {
                maxDeque.pollFirst();
            }
            // 移除队尾比当前元素小的元素
            while (!maxDeque.isEmpty() && arr[maxDeque.peekLast()] <= arr[i]) {
                maxDeque.pollLast();
            }
            maxDeque.offerLast(i);
            if (i >= k - 1) {
                System.out.print(arr[maxDeque.peekFirst()] + " ");
            }
        }
    }
}
